For some time, systems have been performing relatively complex computations using general-purpose computers. Largely due to the complexity of the processing to be performed in various types of applications, such implementations have been replaced by faster, more dedicated computer and/or discrete logic designs to address the near-real time system demands. Ongoing demands for increasingly complex computations and the advent of certain technologies, such as public key cryptography, have spurred efforts to design and build special purpose computational hardware capable of rapidly performing complex computations, such as modular multiplication and exponentiation of extremely large numbers.
Related efforts to discover and exploit several important mathematical enhancements to the process utilized in performing modular multiplication have also been addressed. More recently, with the development of Application Specific Integrated Circuits (ASICs), designers can now realized single-IC solutions for complex computational problems. Through such development, there have been attempts to implement a computational device which performs modular multiplication. One such procedure is disclosed in an article entitled, "Modular Multiplication Without Trial Division," by P. L. Montgomery and published in Mathematics of Computation, Vol. 40, No. 170, pp. 519-521, April 1985, incorporated herein by reference. Some other approaches use dedicated hardware techniques involving architectures known as systolic arrays to perform modular multiplication. An example approach of this type is discussed in detail in an article entitled, "Systolic Modular Multiplication," by C. D. Walter, IEEE Transactions on Computers, Vol., 42, No. 3, March 1993, pp. 376-378; and in, "Hardware Implementation of Montgomery's Modular Multiplication Algorithm," by S. E. Eldridge & C. D. Walter, IEEE Transactions on Computers, Vol. 42, No. 6, June 1993, pp. 693-699. Such systolic array architectures have been successful in reducing the processing time for the modular computations sufficiently to overcome the limitations of software-based processing solutions.
Encryption systems often use operands and modulus values consisting of 1024 bits or more. For this and other reasons, systolic array architectures involve a significant number of hardware elements to construct dedicated, special purpose modular multiplication processors. As the length of the operands to the modular multiplication and the length of the modulus increases, more logic gates are involved in implementing the processing apparatus.